//Suchbaumoperationen Platschi, 6.10.04, DEV C++

#include <stdlib.h>
#include <conio.h>
#include <windows.h>
#include "queueyzeiger.h"
using namespace std;


//+++Knotenstruktur wird definiert+++

Kasten * wu;


//+++simuliert die Positionierung des Cursors+++
void gotoxy(int x, int y) 
{ 
HANDLE hConsoleOutput; 
COORD dwCursorPosition; 
dwCursorPosition.X = x; 
dwCursorPosition.Y = y; 
hConsoleOutput = GetStdHandle(STD_OUTPUT_HANDLE); 
SetConsoleCursorPosition(hConsoleOutput,dwCursorPosition); 
} 


//+++Unterfunktion zu "erzeuge", fügt ein Element an aktueller Zeigerpos. ein+++
void Hinzufuegen(Kasten * &wu, int wert )
{
  if (wu==NULL)
  {
    wu=new Kasten;
    wu->lnf=NULL;
    wu->rnf=NULL;    
    wu->inh=wert;
  }  
   else 
   if (wu->inh>wert) Hinzufuegen(wu->lnf,wert);
    else Hinzufuegen(wu->rnf,wert);
}


//+++sucht die richtige Position eines einzufuegenden Elements+++
void erzeuge(Kasten * &wu)
{
   int wert;
   do
   {
    cout<<"Wert waehlen: ";
    cin>>wert;
    if (wert!=0) Hinzufuegen(wu,wert);
   } while (wert!=0);  
}


//+++Ausgabe des Suchbaumes (Preorder)+++
void zeige(Kasten * wu,int x, int y, char rl)
{
  if (wu!=NULL)
  {
   gotoxy(x,y);cout<<wu->inh; 
   if (rl=='l')
   {  
     gotoxy(x+1,y-1);cout<<"/\n";
   }
   else
   if (rl=='r')
   {
     gotoxy(x-1,y-1);cout<<"\\\n";
   }
   zeige(wu->lnf,x-4,y+2,'l');
   zeige(wu->rnf,x+4,y+2,'r');
  }
}


//+++Suchen eines Inhaltselements+++
void suche(Kasten * where, int what)
{
 if (where==NULL) cout<<"Nicht gefunden!";
 else
   if (where->inh==what) cout<<"Ist enthalten!"; 
   else
    if (where->inh>what) suche(where->lnf,what);
    else suche(where->rnf,what);
}


//+++Loeschen eines (vorhandenen) Knotens+++
void loesche(Kasten * &where,int what)
{
  if (where==NULL) cout<<"Nicht enthalten!";
  else
   if (where->inh<what) return loesche(where->rnf,what);
   else
    if (where->inh>what) return loesche(where->lnf,what);
     else 
     {
       Kasten *hilf,*rnfalt;
       hilf=where->lnf;
       rnfalt=where->rnf;
       delete where;
       if (hilf==NULL) where=rnfalt;
       else
       {
         where=hilf;
         if (rnfalt!=NULL)
         {
           while (hilf->rnf!=NULL) hilf=hilf->rnf;
           hilf->rnf=rnfalt;
         }
       }
      cout<<"Baum nach dem Loeschen..."; 
      zeige(wu,40,5,' ');   
     }
}


//+++Abfrage eines Inhaltselements fuer Loeschen und Suchen+++
void abfrage(int &wert)
{
 cout<<"\nBitte Wert waehlen: ";
 cin>>wert;
}


//+++Hoehenbestimmung eines Unterbaumes+++
int hoehe(Kasten *where)
{
 int hl,hr;
 if (where==NULL) return 0;
  else 
  {
   hl=hoehe(where->lnf);
   hr=hoehe(where->rnf);
   if (hl>=hr) return hl+1; else return hr+1;
  }
}


//+++llr-Funktion fuer einfache Rechtsrotation+++
void llr(Kasten * &where)
{
 cout<<"einfach rechts";
 Kasten *hilf;
 hilf=where;
 where=hilf->lnf;
 hilf->lnf=where->rnf;
 where->rnf=hilf;
}


//+++rrr-Funktion fuer einfache Linksrotation+++
void rrr(Kasten * &where)
{
 cout<<"einfach links";
 Kasten *hilf;
 hilf=where;
 where=hilf->rnf;
 hilf->rnf=where->lnf;
 where->lnf=hilf; 
}


//+++lrr-Funktion fuer Links-Rechtsrotation+++
void lrr(Kasten * &where)
{
 cout<<"links-rechts";
 Kasten *hilf;
 hilf=where;
 where=hilf->lnf->rnf;
 hilf->lnf->rnf=where->lnf;
 where->lnf=hilf->lnf;
 hilf->lnf=where->rnf;
 where->rnf=hilf;
}


//+++rlr-Funktion fuer Rechts-Linksrotation+++
void rlr(Kasten * &where)
{
 cout<<"rechts-links";
 Kasten *hilf;
 hilf=where;
 where=hilf->rnf->lnf;
 hilf->rnf->lnf=where->rnf;
 where->rnf=hilf->rnf;
 hilf->rnf=where->lnf;
 where->lnf=hilf; 
}


//+++Balancierungsfunktion, benutzt Hoehenbestimmung und Rotationsfunktionen+++
void balance(Kasten * &where)
{
 int hl,hr;
 if (where!=NULL)
 do
 {
  balance(where->lnf);
  balance(where->rnf);
  hl=hoehe(where->lnf);
  hr=hoehe(where->rnf);
  if (abs(hr-hl)>1)
   if (hl>hr)
    if (hoehe(where->lnf->lnf)>=hoehe(where->lnf->rnf))
     llr(where); else lrr(where);
    else
    if (hoehe(where->rnf->rnf)>=hoehe(where->rnf->lnf))
     rrr(where); else rlr(where);
 } while (abs(hr-hl)>1);
}


//+++Loeschen ganzer Baum+++
void kill(Kasten * &where)
{
 if (where!=NULL)
  {
   kill(where->lnf);
   kill(where->rnf);
   if (where->lnf==NULL && where->rnf==NULL) {delete where;where=NULL;}
  }   
}


//+++LevelOrder-Traversierung mittels Schlange
void levelorder(Kasten * where)
{
 cout<<"LevelOrder-Traversierung\n";
 init(q);
 enqueue(q,where);
 while (!empty(q))
 {
  Kasten * hilf=head(q);
  cout<<hilf->inh<<"_ ";
  dequeue(q);
  if (hilf->lnf!=NULL) enqueue(q,hilf->lnf);
  if (hilf->rnf!=NULL) enqueue(q,hilf->rnf); 
 }     
}


//+++Main-Part mit Auswahlmenue+++
int main()
{ 
   wu=NULL;
   int wert;
   char wahl;
   do
   {
    system("cls");
    cout<<"1-Erzeugen  2-Ausgeben  3-Suchen \n4-LoeschenKnoten  \
5-Balancieren  6-LoeschenBaum 7-LevelOrder 0-Ende\n";    
    wahl=getch(); 
    switch (wahl)
    {
     case '1': erzeuge(wu);break;
     case '2': if (wu==NULL) cout<<"LEER!";
                 else zeige(wu,40,5,' ');getch();break;
     case '3': abfrage(wert);suche(wu,wert);getch();break;
     case '4': abfrage(wert);loesche(wu,wert);getch();break;
     case '5': balance(wu);cout<<"AVL-BAum erzeugt!";
               zeige(wu,40,5,' ');getch();break;
     case '6': kill(wu);cout<<"Baum geloescht!";getch();break;
     case '7': levelorder(wu);system("pause");getch();getch();break;
    } 
   } while (wahl!='0');
   gotoxy(1,24);
   return 0;
}